//https://www.nowcoder.com/practice/390da4f7a00f44bea7c2f3d19491311b?tpId=13&tqId=23295&ru=%2Fpractice%2Fc451a3fd84b64cb19485dad758a55ebe&qru=%2Fta%2Fcoding-interviews%2Fquestion-ranking&sourceUrl=%2Fexam%2Foj%2Fta%3Fpage%3D1%26tpId%3D13%26type%3D13
//思路：双指针问题，解决问题；
//https://leetcode.cn/problems/two-sum/submissions/499028128/?envType=study-plan-v2&envId=top-100-liked
//思路：变种：暴力求法（选择排序）：如何进行两两比较？；hash；

#include <iostream>
#include <vector>
#include <map>
#include<unordered_map>
using namespace std;


#include <vector>
class Solution {
public:
    vector<int> FindNumbersWithSum(vector<int> array,int sum) {
        std::vector<int> res{};
        if(array.empty()||array.size()<=1 || sum<0) return res;

        int left = 0,right = array.size()-1;
        while(left<right) {
            if(array[left]+array[right] == sum){
                res.push_back(array[left]);
                res.push_back(array[right]);
                break;
            }else if(array[left]+array[right] < sum) {
                left++;
            } else {
                right--;
            }
        }
        return res;
        
    }
};

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        int n = nums.size();
        for (int i = 0; i < n; ++i) {
            for (int j = i + 1; j < n; ++j) {
                if (nums[i] + nums[j] == target) {
                    return {i, j};
                }
            }
        }
        return {};
    }
};

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        std::unordered_map<int,int> hashtable;
        for(int i=0;i<nums.size();++i){
            auto it= hashtable.find(target-nums[i]);
            if(it!=hashtable.end()){
                return {it->second,i};
            }
            hashtable[nums[i]]=i;
        }
        return {};
    }
};